#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> BuildNext(const std::string& pattern) {
  int size = pattern.size();
  vector<int> next(size);
  next[0] = 0;
  int prefix_len = 0;
  for (int i = 1; i < size;) {
    if (pattern[prefix_len] == pattern[i]) {
      ++prefix_len;
      next[i++] = prefix_len;
    } else {
      prefix_len = next[prefix_len - 1];
      if (prefix_len == 0) {
        next[i++] = 0;
      }
    }
  }
  return next;
}
int KMP(const std::string& str1, const std::string& str2) {
  int i = 0, j = 0;
  vector<int> next(BuildNext(str2));
  //   for (auto i : next) cout << i << "  ";
  //   cout << endl;
  while (i < str1.size()) {
    if (str1[i] == str2[j]) {  // 字符匹配
      ++i;
      ++j;
    } else if (j > 0) {  // 字符失配，根据next跳过子串前面的一些字符
      j = next[j - 1];
    } else  // 子串第一个字符就失配
      ++i;
    if (j == str2.size()) return i - j;
  }
  return -1;
}
void Test() {
  string str1 = "abababcaa";
  string str2 = "ababc";
  string str3 = "abcdefg";
  string str4 = "hijklmn";
  string str5 = "abcabccba";
  string str6 = "ccba";
  cout << KMP(str1, str2) << endl;
  cout << KMP(str3, str4) << endl;
  cout << KMP(str5, str6) << endl;
}
int main() {
  Test();
  return 0;
}

// g++ -o kmp kmp.cc -std=c++11
// https://www.bilibili.com/video/BV1AY4y157yL?spm_id_from=333.851.b_7265636f6d6d656e64.2